home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / MCASM.RAR / MC_ASM.EXE / WROX_ASM / CH12 / COMMON / PALETTE.H < prev    next >
C/C++ Source or Header  |  1994-09-24  |  7KB  |  173 lines
  1. #ifndef palette_h
  2. #define palette_h
  3.  
  4. /*
  5.  * The Color Quantization : true color to 256 or
  6.  * to smaller (specified) colors palette
  7.  *
  8.  * Most of code and ideas were taken
  9.  *                from the Independent JPEG Group's software.
  10.  *              ( see the accompanying README file).
  11.  *
  12.  * I just adjust code for RGB color model (instead of YCbCr)
  13.  *  and re-organized text
  14.  *    to fit  our  class library and
  15.  *      to avoid duplication of code in similar procedures
  16.  *    (but it all is not good for execution speed)
  17.  *  and make some (unimportant) changes  ....
  18.  *         (and maybe brought some buggs)
  19.  *
  20.  * E.Podvoysky from ^Z for WROX press book
  21.  *
  22.  */
  23.  
  24. /*
  25.  * This module implements the well-known Heckbert paradigm for color
  26.  * quantization.  Most of the ideas used here can be traced back to
  27.  * Heckbert's seminal paper
  28.  *   Heckbert, Paul.  "Color Image Quantization for Frame Buffer Display",
  29.  *   Proc. SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
  30.  *
  31.  * In the first pass over the image, we accumulate a histogram showing the
  32.  * usage count of each possible color.  (To keep the histogram to a reasonable
  33.  * size, we reduce the precision of the input; typical practice is to retain
  34.  * 5 or 6 bits per color, so that 8 or 4 different input values are counted
  35.  * in the same histogram cell.)  Next, the color-selection step begins with a
  36.  * box representing the whole color space, and repeatedly splits the "largest"
  37.  * remaining box until we have as many boxes as desired colors.  Then the mean
  38.  * color in each remaining box becomes one of the possible output colors.
  39.  * The second pass over the image maps each input pixel to the closest output
  40.  * color (optionally after applying a Floyd-Steinberg dithering correction).
  41.  * This mapping is logically trivial, but making it go fast enough requires
  42.  * considerable care.
  43.  *
  44.  * Heckbert-style quantizers vary a good deal in their policies for choosing
  45.  * the "largest" box and deciding where to cut it.  The particular policies
  46.  * used here have proved out well in experimental comparisons, but better ones
  47.  * may yet be found.
  48.  *
  49.  * The most significant difference between this quantizer and others is that
  50.  * this one is intended to operate in YCbCr colorspace, rather than RGB space
  51.  * as is usually done.  Actually we work in scaled YCbCr colorspace, where
  52.  * Y distances are inflated by a factor of 2 relative to Cb or Cr distances.
  53.  * The empirical evidence is that distances in this space correspond to
  54.  * perceptual color differences more closely than do distances in RGB space;
  55.  * and working in this space is inexpensive within a JPEG decompressor, since
  56.  * the input data is already in YCbCr form.  (We could transform to an even
  57.  * more perceptually linear space such as Lab or Luv, but that is very slow
  58.  * and doesn't yield much better results than scaled YCbCr.)
  59.  */
  60.  
  61. #ifdef INT_MAP_CELL
  62.  #define MAXNUMCOLORS  256 /* maximum size of colormap */
  63. #else
  64.  #define MAXNUMCOLORS  255 /* maximum size of colormap */
  65. #endif
  66.  
  67. /*
  68.  * First we have the histogram data structure and routines for creating it.
  69.  *
  70.  * For work in YCbCr space, it is useful to keep more precision for Y than
  71.  * for Cb or Cr.  We recommend keeping 6 bits for Y and 5 bits each for Cb/Cr.
  72.  * If you have plenty of memory and cycles, 6 bits all around gives marginally
  73.  * better results; if you are short of memory, 5 bits all around will save
  74.  * some space but degrade the results.
  75.  * To maintain a fully accurate histogram, we'd need to allocate a "long"
  76.  * (preferably unsigned long) for each cell.  In practice this is overkill;
  77.  * we can get by with 16 bits per cell.  Few of the cell counts will overflow,
  78.  * and clamping those that do overflow to the maximum value will give close-
  79.  * enough results.  This reduces the recommended histogram size from 256Kb
  80.  * to 128Kb, which is a useful savings on PC-class machines.
  81.  * (In the second pass the histogram space is re-used for pixel mapping data;
  82.  * in that capacity, each cell must be able to store zero to the number of
  83.  * desired colors.  16 bits/cell is plenty for that too.)
  84.  * Since the JPEG code is intended to run in small memory model on 80x86
  85.  * machines, we can't just allocate the histogram in one chunk.  Instead
  86.  * of a true 3-D array, we use a row of pointers to 2-D arrays.
  87.  *
  88.  * (From hence comment is slightly changed according RGB color model - E.P.)
  89.  * Each pointer corresponds to a R value (typically 2^5 = 32 pointers) and
  90.  * each 2-D array has 2^(5+5) = 1024 or 2^(6+5) = 2048 entries.  Note that
  91.  * on 80x86 machines, the pointer row  may be in near memory but the actual
  92.  * arrays are in far memory.
  93.  */
  94.  
  95.  
  96. #define HIST_G_BITS  6        /* bits of precision in G histogram */
  97. #define HIST_R_BITS  5        /* bits of precision in R histogram */
  98. #define HIST_B_BITS  5        /* bits of precision in B histogram */
  99.  
  100. // #define Y_SCALE 2        /* scale Y distances up by this much */
  101.  
  102. #define RSCALE 24         /* E.P.- scale G distances up by this much and / 16*/
  103. #define GSCALE 32          /* E.P.- scale R distances up by this much and / 16*/
  104.  
  105.  
  106. #define HIST_G_ELEMS  (1<<HIST_G_BITS) /* # of elements along histogram axes */
  107. #define HIST_R_ELEMS  (1<<HIST_R_BITS)
  108. #define HIST_B_ELEMS  (1<<HIST_B_BITS)
  109.  
  110. #define G_SHIFT  (8 - HIST_G_BITS)
  111. #define R_SHIFT  (8 - HIST_R_BITS)
  112. #define B_SHIFT  (8 - HIST_B_BITS)
  113.  
  114. //------------------------- HISTOGRAM
  115.  
  116. typedef WORD histcell;    /* histogram cell; MUST be an unsigned type */
  117. typedef histcell far *histptr;    /* for pointers to histogram cells */
  118.  
  119. typedef histcell hist1d[HIST_B_ELEMS]; /* typedefs for the array */
  120. typedef hist1d far * hist2d;    /* type for the R-level pointers */
  121. typedef hist2d * hist3d;    /* type for top-level pointer */
  122.  
  123. //------------------------- BOX
  124. typedef struct {
  125.     /* The bounds of the box (inclusive); expressed as histogram indexes */
  126.     int c0min, c0max;
  127.     int c1min, c1max;
  128.     int c2min, c2max;
  129.     /* The number of nonzero histogram cells within this box */
  130.     unsigned long colorcount,
  131.         //this was added by E.P.
  132.         volume;
  133.     BOOL splitable;
  134.  
  135.       } box;
  136.  
  137. typedef box *boxptr;
  138.  
  139. class color_selector {
  140. protected:
  141.     hist3d histogram;    /* pointer to the histogram */
  142.     boxptr boxlist;        /* array with room for desired # of boxes */
  143.     int numboxes;        /* number of boxes currently in boxlist */
  144.  
  145.     // first stage
  146.     boxptr find_biggest_color_pop ();
  147.     boxptr find_biggest_volume ();
  148.     void update_box (boxptr boxp);
  149.     void compute_color (boxptr boxp, BGRcolortype &color);
  150.     void median_cut ();   /* Repeatedly select and split the largest box
  151.                 /*  until    we have enough boxes */
  152.  
  153.  
  154. public:
  155.     BGRpalette my_colormap; /* the finished colormap (in RGB space) */
  156.     int desired_colors,actual_number_of_colors,width;
  157.     BOOL initialized;
  158.  
  159.     color_selector(int desired_colors_,int width_); //allocate create histogram and
  160.     virtual ~color_selector();
  161.  
  162.     void prescan_line (BYTE *R, BYTE *G, BYTE *B);
  163.     void select_colors();
  164.          // special procedures  to convert 256 colors to 16
  165.     void prepare_scan_palette (BGRpalette pal);
  166.     void prescan_line_palette (BYTE *source);
  167.  
  168. };
  169. #endif
  170.  
  171.  
  172.  
  173.